﻿using System.Collections.Generic;
using UnityEngine;

namespace PolygonTool
{
    #region 耳切法对简单多边形进行三角形化

    /// <summary>对多边形处理</summary>
    public class Triangulation
    {
        /// <summary>顶点序列</summary>
        private List<int> _vertexsSequence = new List<int>();
        /// <summary>链表结构集合</summary>
        private List<Node> _nodeList = new List<Node>();

        #region 初始化
        /*
         * 组件链表
         *      
         * **/
        /// <summary>初始化</summary>
        /// <param name="vertexs">多边形顶点</param>
        public Triangulation(List<Vector3> vertexs)
        {
            for (int i = 0; i < vertexs.Count; i++)
            {
                Node node = new Node(i, vertexs[i]);
                _nodeList.Add(node);
            }

            //构成一个双向环形链表
            for (int i = 0; i < _nodeList.Count; i++)
            {
                //第一个里的上一个节点是链表里的最后一个
                //          下一个节点是下一个节点
                if (i == 0)
                {
                    _nodeList[i].lastNode = _nodeList[_nodeList.Count - 1];
                    _nodeList[i].nextNode = _nodeList[1];
                }
                //第一个里的上一个节点是上一个节点
                //          下一个节点是链表里的第一个
                else if (i == _nodeList.Count - 1)
                {
                    _nodeList[i].lastNode = _nodeList[_nodeList.Count - 2];
                    _nodeList[i].nextNode = _nodeList[0];
                }
                else
                {
                    _nodeList[i].lastNode = _nodeList[i - 1];
                    _nodeList[i].nextNode = _nodeList[i + 1];
                }
            }
        }
        #endregion

        /// <summary>获取三角形的顶点序列</summary>
        public int[] GetTriangles()
        {
            while (_nodeList.Count >= 3)
            {
                bool sr = SplitPolygon();
                if (sr == false)
                {
                    Debug.Log("null");
                    return null;
                }
            }
            return _vertexsSequence.ToArray();
        }

        /// <summary>计算凹顶点，凸顶点，耳朵</summary>
        //private SplitResult SplitPolygon()
        private bool SplitPolygon()
        {
            //凹点
            List<Node> _concaveVertexs = new List<Node>();
            //凸点
            List<Node> _raisedVertexs = new List<Node>();
            //耳朵
            List<Node> _polygonEars = new List<Node>();
            //起始节点
            Node currentNode = _nodeList[0];

            #region 计算凹顶点，凸顶点
            /*
             * 取其中一点和这个点左右两边做角度,查看这个点的cross是否大于0, 大于0就是大于180, 就是凹点,否则就是凸点
             * **/
            //要添加0, 这样就能记录最后一个点
            for (int i = 0; i < _nodeList.Count; i++)
            {
                Vector3 cl3 = currentNode.position - currentNode.lastNode.position;
                Vector3 nc3 = currentNode.nextNode.position - currentNode.position;
                Vector3 crossRes = Vector3.Cross(cl3, nc3);//向量的外积????????????????????????????
                if (crossRes.y > 0)//如果比较的是其他平面的, 则切换轴
                {
                    _concaveVertexs.Add(currentNode);//凹点
                }
                else
                {
                    _raisedVertexs.Add(currentNode);//凸点
                    _polygonEars.Add(currentNode);//耳朵
                }
                currentNode = currentNode.nextNode;
            }
            #endregion

            #region 计算耳朵
            //检查耳朵的内部是否包含了其他的点, 如果包含了其他的点, 就把这个耳朵暂时先舍弃, 后续再进行使用
            List<int> needRemoveIdList = new List<int>();
            for (int i = 0; i < _polygonEars.Count; i++)
            {
                Node earNode = _polygonEars[i];
                Node compareNode = earNode.nextNode.nextNode;

                while (compareNode != earNode.lastNode)
                {
                    bool isIn = IsIn(compareNode.position, earNode.lastNode.position, earNode.position, earNode.nextNode.position);
                    if (isIn == true)
                    {
                        if (_polygonEars.Contains(earNode))
                        {
                            needRemoveIdList.Add(earNode.id);
                        }
                        break;
                    }
                    compareNode = compareNode.nextNode;
                }
            }
            for (int j = 0; j < needRemoveIdList.Count; j++)
            {
                for (int i = 0; i < _polygonEars.Count; i++)
                {
                    if (_polygonEars[i].id == needRemoveIdList[j])
                    {
                        _polygonEars.RemoveAt(i);
                    }
                }
            }

            #endregion

            //耳朵为空说明不是简单多边形 多边形三角化失败
            /*
             * 当排序为顺时针排序时,视觉上的凹点实际为凸点,视觉上的凸点为凹点,实际计算时所有的都变成了凹点,
             * **/
            if (_polygonEars.Count == 0) return false;

            _vertexsSequence.Add(_polygonEars[0].lastNode.id);
            _vertexsSequence.Add(_polygonEars[0].id);
            _vertexsSequence.Add(_polygonEars[0].nextNode.id);
            //0就是剩余点中最突出的一个耳朵, 将这个耳朵的前后点加入三角形序列, 然后移除这个点, 再次循环,找到剩下的所有顶点中最突出的耳朵
            Node _node = _polygonEars[0];
            _nodeList.Remove(_node);
            _node.lastNode.nextNode = _node.nextNode;
            _node.nextNode.lastNode = _node.lastNode;

            return true;
        }

        /// <summary>P点是否在ABC三角形内部</summary>
        /// <param name="p">一点</param>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <param name="c"></param>
        /// <returns></returns>
        public bool IsIn(Vector3 p, Vector3 a, Vector3 b, Vector3 c)
        {
            Vector3 pa = p - a;
            Vector3 pb = p - b;
            Vector3 pc = p - c;

            Vector3 t1 = Vector3.Cross(pa, pb);
            Vector3 t2 = Vector3.Cross(pb, pc);
            Vector3 t3 = Vector3.Cross(pc, pa);
            //Y>0为凹点

            bool isIn2 = (t1.y >= 0 && t2.y >= 0 && t3.y >= 0) || (t1.y <= 0 && t2.y <= 0 && t3.y <= 0);
            return isIn2;
        }
    }
    /// <summary>链表结构</summary>
    public class Node
    {
        /// <summary>// 节点角标</summary>
        public int id;
        /// <summary>节点Position</summary>
        public Vector3 position;
        public Node lastNode;
        public Node nextNode;

        /// <summary>初始化</summary>
        /// <param name="id">节点角标</param>
        /// <param name="vertex">节点Position</param>
        public Node(int id, Vector3 vertex)
        {
            this.id = id;
            this.position = vertex;
        }
    }

    #endregion
}